This invention relates to information storage and retrieval systems, and more particularly to means for encoding and decoding codewords for use in error detection and correction in such information storage and retrieval systems.
Digital information storage devices, such as magnetic or optical disk or tape, store information in the form of binary bits. Also information transmitted between two digital devices, such as computers, is transmitted in the form of binary bits. During transfer of data between devices, or during transfer between the magnetic or optical media and the control portions of a device, errors sometimes occur. Errors can also be caused by defects in the magnetic or optical storage medium. These errors must be corrected if the storage device or transmission channel is to be useful.
Correction of this information is accomplished by deriving additional bits of information, called check bits or redundancy, by processing the data mathematically, appending the check bits to the original data bits during the transmission or storage process, and reprocessing the data and check bits mathematically to detect and correct erroneous data bits at the time the information is received or retrieved. The process of deriving the check bits is called encoding and one class of codes often used in the process of encoding is Reed-Solomon codes.
Encoding of error correction information using a Reed-Solomon code is accomplished by processing a set of k data symbols, called a data block, to devise a set of r check symbols, also called redundancy symbols; each symbol is made up of m binary bits of information and is an element of a finite field GF(2.sup.m). An encoder divides a polynomial whose coefficients are the k data symbols by the generator polynomial of the code, which is of degree r. The r coefficients of the remainder of this division are the r check symbols which are appended to the data block to form a codeword which is transmitted over the signal channel or stored in an information storage device.
When a codeword is received from the signal channel or read from the storage device, a frequency-domain syndrome generator processes the received codeword by dividing it by each of the r factors of the generator polynomial of the code. The r remainders of these divisions form r frequency-domain syndrome symbols which a decoder uses to detect the presence of error(s) and to correct any error(s) present before transferring the data bits for further processing.
Encoding (dividing by the code generator polynomial) and frequency-domain syndrome generation (dividing by each factor of the code generator polynomial) each require complicated hardware which is expensive to implement. Methods for sharing circuity between these functions to reduce the cost of implementing powerful error correction codes such as the Reed-Solomon codes are required to meet continuing demands for lower cost and higher performance in information storage and retrieval devices.
Since many data storage devices are used for archival purposes wherein many write operations take place between read operations, a hardware failure may fail to be detected until many erroneous data have been written. This is a catastrophic error situation which may not be detected until data are read back after periods as long as ten years.
It is thus apparent that there is a need in the art for an improved encoding and frequency-domain syndrome generating system.